package org.hot100_1;

public class leetcode88 {
//    public String longestPalindrome(String s) {
//
//        if (s == null || s.length() < 2) {
//            return s;
//        }
//
//        int n =s.length();
//
//        boolean [][] dp =new boolean[n][n];
//        dp[0][0]=true;
//        int maxLen =0;
//        int maxStart=0;
//        int maxEnd =0;
//
//        for (int r = 1; r < n; r++) {
//            for (int l = 0; l < r; l++) {
//                if (s.charAt(r)==s.charAt(l) &&(r-l<=2 || dp[l+1][r-1])){
//                    dp[l][r]=true;
//
//                    if (r-l+1>maxLen){
//                        maxStart=l;
//                        maxEnd=r;
//                        maxLen=r-l+1;
//                    }
//
//                }
//            }
//        }
//
//        return s.substring(maxStart,maxEnd+1);
//    }

    public String longestPalindrome(String s) {
        int n = s.length();
        //dp[1][3]表示在s中第1位到到第3位的字符串是否是回文串
        boolean [][] dp = new boolean[n][n];
        dp[0][0]=true;
        int maxStart =0;
        int maxEnd =0;
        int maxLen=0;
        for (int r = 1; r < n; r++) {
            for (int l = 0; l < r; l++) {
                if (s.charAt(l)==s.charAt(r) && ((r-l<=2) ||(dp[l+1][r-1]))){
                    dp[l][r]=true;
                    if (r-l+1>maxLen){
                        maxStart=l;
                        maxEnd=r;
                        maxLen=r-l+1;
                    }
                }
            }
        }

        return s.substring(maxStart,maxEnd+1);
    }
}
